package com.gjh.study.algorithm4.tree;

/**
 * 在二叉树中找到两个节点的最近公共祖先
 * 给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
 * 输入描述
 * 第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
 *
 * 以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)
 *
 * 最后一行为节点 o1 和 o2。
 * 输出描述
 * 输出一个整数表示答案。
 * 示例1
 * 输入
 * 8 1
 * 1 2 3
 * 2 4 5
 * 4 0 0
 * 5 0 0
 * 3 6 7
 * 6 0 0
 * 7 8 0
 * 8 0 0
 * 4 5
 * 输出
 * 2
 * @author guangjh
 * @version 1.0
 * @date 2020/7/7 17:47
 */
public class CommonParent {
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(1);
        tree.left = new TreeNode(2);
        tree.right = new TreeNode(3);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null || root == A || root == B) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, A, B);
        TreeNode right = lowestCommonAncestor(root.right, A, B);
        if (left != null && right != null) {
            return root;
        }
        if (left != null) {
            return left;
        }
        if (right != null) {
            return right;
        }
        return null;
    }

}
